//
// Created by LiuYou on 2021/5/10.
//

#define TEST04_1

/**
 * 绿皮书上的选择排序算法不会写。
 */
#ifdef TEST05

#include <array>
#include <iostream>

/**
 * 这个选择排序算法不会写。
 */
int main() {

    std::array<int, 5> arr{3, 6, 21, 15, 4};
    int tmp = arr[0];
    int index{0};

    for (int i = 0; i < arr.size(); ++i) {
        for (int j = i; j < arr.size(); ++j) {
            if (tmp < arr[j + 1]) {
                tmp = arr[j + 1];
                arr[j] = arr[j];
                arr[0] = tmp;
                //            index = i;
            } else {
                tmp = arr[i + 1];
                break;
            }
        }
    }

    for (const auto& item : arr) {
        std::cout << item << " ";
    }
    std::cout << std::endl;


    return 0;
}

#endif


#ifdef TEST04_1
/**
 * 这里解决了Test04的内存泄漏问题。而且是使用std::vector, 使用std::vector可以通过调用它提供的erase函数, 可以非常方便数组结构的
 * 插入和删除！！！！
 */

#ifndef TEST04_1
namespace Test04_1 {
#endif

#include <vector>
#include <iostream>

//
static int findMaxIndex(const std::vector<int>& vec);

void selectionSort(std::vector<int>& vec, std::vector<int>& vector);

int main() {
    std::vector<int> vec{4, 3, 1, 5, 2, 7};
    std::cout << vec.size() << std::endl;

    std::vector<int> vector;

    selectionSort(vec, vector);

    for (const auto& item : vector) {
        std::cout << item << " ";
    }
    std::cout << std::endl;


    return 0;
}

void selectionSort(std::vector<int>& vec, std::vector<int>& vector) {
    unsigned long size = vec.size();
    for (int i = 0; i < size; ++i) {
        int index = findMaxIndex(vec);
        vector.push_back(vec[index]);
        vec.erase(vec.cbegin() + index);
    }
}

static int findMaxIndex(const std::vector<int>& vec) {
    // TODO 注意: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    //  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    //  注意: 这里和index和tmp的初始化非常的重要！！！！！！！！
    //  这个index和tmp变量一定要是数组中的同一个元素的下标(索引)和它的值。
    int index{0};
    int tmp{vec[0]};
    for (int i = 0; i < vec.size(); ++i) {
        if (vec[i] > tmp) {
            tmp = vec[i];
            index = i;
        }
    }
    return index;
}

#ifndef TEST04_1
}
#endif
#endif


#ifdef TEST04
/**
 * 这里使用了动态数组std::vector, 这样对数组的删除有可调用的函数进行处理, 不需要自己进行删除数组中某个元素有其它所有元素的拷贝移动了。
 * 但是程序有BUG, 有内存泄漏。
 */
namespace Test04 {
//#include <vector>
//#include <iostream>

    static int findMaxIndex(const std::vector<int>& vec);

    namespace TestIterator {
        static void test() {
            std::vector<int> vector{1, 2, 3, 4, 5};
//        vector.erase(vector.cbegin());
            // TODO 注意: 想要删除下标为1的元素转换成迭代器其实就是 vector.cbegin() + 1。
            vector.erase(vector.cbegin() + 1);
            for (const auto& item : vector) {
                std::cout << item << " ";
            }


//        std::cout << std::endl;
            std::fflush(stdout);
        }
    }

    int main() {

//    TestIterator::test();


        std::vector<int> vec{4, 3, 1, 5, 2, 7};
        std::cout << vec.size() << std::endl;

//    findMaxIndex(vec);
        std::vector<int> vector;
        vector.reserve(vec.size());
        std::cout << vector.size() << std::endl;

        // TODO for代码错误
/*    for (int i = 0; i < vector.size(); ++i) {
        vector.push_back(vec[findMaxIndex(vec)]);
        vec.erase(vec.cbegin() + findMaxIndex(vec));
    }*/

//    int size = vec.size();
        for (int i = 0; i < 6; ++i) {
            int index = findMaxIndex(vec);
            vector.push_back(vec[index]);
            vec.erase(vec.begin() + index);
        }

        for (const auto& item : vector) {
            std::cout << item << " ";
        }
        std::cout << std::endl;


        return 0;
    }

    static int findMaxIndex(const std::vector<int>& vec) {
        int index{-1};
        // TODO 注意: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        //  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        //  WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC WC
        //  仅仅是tmp没有初始化为0。真的这种错误很离谱！！！！
        //  所以一定要初始化变量!!!!
        //  而且一定要将vec中的一个值赋值给tmp, 真的非常重要！！！！！ WC！
        int tmp{vec[1]};
        for (int i = 0; i < vec.size(); ++i) {
            if (vec[i] > tmp) {
                tmp = vec[i];
                index = i;
            }
        }
        return index;
    }

}
#endif


#ifdef TEST03
/*
 * 使用了C++的std::array来代替内置数组。可以完成任务。
 */
namespace Test03 {
//#include <array>

    static int findMaxIndex(const std::array<int, 5>& arr, int size);

    int main() {
        std::array<int, 5> arr{5, 2, 3, 1, 6};
        for (const auto& item : arr) {
            std::fprintf(stdout, "%d ", item);
        }
        std::fflush(stdout);

//    findMaxIndex(arr);
        std::array<int, 5> array{};
        int size = arr.size();
        for (auto& item : array) {
            // 下面两条语句是等效的。
//        item = arr[findMaxIndex(arr)];
            item = arr.at(findMaxIndex(arr, size));
            for (int i = findMaxIndex(arr, size); i < size - 1; ++i) {
                arr[i] = arr[i + 1];
            }
            --size;
        }
        std::printf("\n");
        for (const auto& item : array) {
            std::fprintf(stdout, "%d ", item);
        }

        return 0;
    }

    static int findMaxIndex(const std::array<int, 5>& arr, int size) {
        int index{-1};
        int tmp{};
        for (int i = 0; i < size; ++i) {
            if (arr[i] > tmp) {
                tmp = arr[i];
                index = i;
            }
        }
        return index;
    }

}
#endif


#ifdef TEST02
namespace Test02 {
//#include <cstdio>

    static int findMaxIndex(const int* arr, int arrSize);

    static void selectionSort(int* array, int* arr);

    int main() {
        int arr[5]{3, 5, 1, 8, 6};
        int array[5]{};
        selectionSort(array, arr);


        for (const auto& item : array) {
            std::fprintf(stdout, "%d ", item);
        }


        return 0;
    }

    static void selectionSort(int* array, int* arr) {
        int arrSize = 5;
        for (int i = 0; i < 5; ++i) {
            array[i] = arr[findMaxIndex(arr, arrSize)];
            // 然后将arr里的这个元素删掉。
            for (int j = findMaxIndex(arr, arrSize); j < arrSize - 1; ++j) {
                arr[j] = arr[j + 1];
            }
            --arrSize;
        }
    }

    static int findMaxIndex(const int* arr, int arrSize) {
        int max{};
        int index{-1};
        for (int i = 0; i < arrSize; ++i) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        return index;
    }

}
#endif


#ifdef TEST1
/*
 * 这个思路不是选择排序, 不是它确实是选择排序。但是更上课时候的课本上的例子不同。
 * 可能正确运行。
 */
namespace Test1 {
//#include <cstdio>

    static int findMax(int* arr);

    static void selectionSort(int* destinationArr, int* sourceArr);

    int main() {
        int arr[5]{3, 4, 1, 5, 0};
        // TODO 注意: 这样计算数组的长度很不常见: sizeof(arr) / sizeof(*arr)
        //  这种用法极不推荐, 不要使用！！！！
        std::fprintf(stdout, "%lu\n", sizeof(arr) / sizeof(*arr));
        int* ptr = arr;
        std::fprintf(stdout, "%lu\n", sizeof(ptr));

        int array[5]{-1};
        selectionSort(array, arr);

        for (auto item : array) {
            std::fprintf(stdout, "%d\t", item);
        }
        std::fflush(stdout);
        return 0;
    }

    static void selectionSort(int* destinationArr, int* sourceArr) {
        for (int i = 0; i < 5; ++i) {
            destinationArr[i] = findMax(sourceArr);
        }
    }

    static int findMax(int* arr) {
        int tmp{-1};
        int index{-1};
        for (int i = 0; i < 5; ++i) {
            if (arr[i] > tmp) {
                tmp = arr[i];
                index = i;
            }
        }
        for (int i = index; i < (5 - 1); ++i) {
            arr[i] = arr[i + 1];
        }
        return tmp;
    }

}
#endif
